package com.wss.lsl.test.driven.arithmetic.sort;

/**
 * 第一个快排算法:单方向扫描，递归实现的方式
 * 
 * @author wei.ss
 * @date 2017年3月10日
 * @copyright wonhigh.cn
 */
public class QuicklySort1<T extends Comparable<T>> extends
		AbstractQuicklySort<T> {

	public QuicklySort1(T[] data) {
		super(data);
	}

	@Override
	public T[] sort() {
		sort(0, data.length - 1);

		return data;
	}

	private void sort(int l, int u) {

		if (l >= u) {
			return;
		}

		T t = data[l];
		int m = l;
		for (int i = l + 1; i <= u; i++) {
			if (data[i].compareTo(t) < 0) {
				swap(i, ++m);
			}
		}

		swap(l, m);
		sort(l, m - 1);
		sort(m + 1, u);
	}

}
